{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第11章-条件随机场-条件随机场的矩阵形式\n",
    "\n",
    "条件随机场（CRF）的参数化模型：$$\n",
    "P(y|x)=\\frac{1}{Z(x)} \\exp \\left( \\sum_{i,k} \\lambda_k t_k(y_{i-1},y_i,x,i) +\\sum_{i,l} \\mu_l s_l(y_i,x,i) \\right) \\tag{1}$$&emsp;&emsp;其中包含了参数$\\lambda_k,\\mu_l$，特征函数$t_k,s_l$，特征函数$t_k$为转移特征，时刻$i$和$i-1$对应的状态，以及给定的向量$X$和位置$i$；$s_l$为状态特征，只和当前的时刻$i$的状态有关，以及给定的向量$X$和位置$i$。  \n",
    "&emsp;&emsp;条件随机场给出的是一个关于$y$的条件分布，和隐马尔可夫模型不同，在HMM中，联合概率分布为$P(O,I|\\lambda)$，在CRF中，观测用随机变量$X$表示，所求的模型也就是状态$y$的联合分布，一旦给定特征函数，模型的参数取决于$\\lambda_k,\\mu_l$。  \n",
    "条件随机场的矩阵形式：$$ P_w(y|x)=\\frac{1}{Z_w(x)} \\prod_{i=1}^{n+1} M_i(y_{i-1},y_i|x) \\tag{2}$$&emsp;&emsp;其中$w$为权重，$(1)$中的$Z(x)$和$(2)$中的$Z_w(x)$是一致的，区别就在后面一部分。 \n",
    "\n",
    "### 推导从参数化形式转化为矩阵形式\n",
    "以下推导过程中，在特征函数里省略$x,i$：  \n",
    "$\\begin{array}{ll}\n",
    "{}&\\displaystyle \\exp \\left( \\sum_{i,k} \\lambda_k t_k(y_{i-1},y_i) +\\sum_{i,l} \\mu_l s_l(y_i) \\right) \\\\\n",
    "=& \\displaystyle \\exp\\left\\{ \\sum_i \\left[ \\sum_k \\lambda_k t_k(y_{i-1},y_i) + \\sum_l \\mu_l s_l(y_i) \\right] \n",
    "\\right\\} \\\\ \n",
    "=& \\displaystyle \\prod_i \\exp\\left(\\sum_k \\lambda_k t_k(y_{i-1},y_i) + \\sum_l \\mu_l s_l(y_i) \\right)\n",
    "\\end{array}$   \n",
    "对比$(1)$，可得$$M_i(y_{i-1},y_i|x) = \\exp\\left(\\sum_k \\lambda_k t_k(y_{i-1},y_i) + \\sum_l \\mu_l s_l(y_i) \\right)$$&emsp;&emsp;书中将$t_k(y_{i-1},y_i)$和$s_l(y_i)$组合成状态函数，将$\\lambda_k$和$\\mu_l$组合成权重向量。为什么说$M_i(x)$是一个矩阵，因为$y_{i-1}$和$y_i$都是状态变量，可以通过该公式表示为一个矩阵，得到$M_i(x)=[M_i(y_{i-1},y_i|x)]$  \n",
    "\n",
    "### 例11.2讲解\n",
    ">例11.2 给定一个由图11-5所示的线性链条件随机场，观测序列$x$，状态序列$y$，$i=1,2,3,n=3$，标记$y_i \\in \\{1,2\\}$，假设$y_0=\\text{start}=1,y_4=\\text{stop}=1$，各个位置的随机矩阵$M_1(x),M_2(x),M_3(x),M_4(x)$分别是$$\\begin{array}{ll}\n",
    "M_1(x)=\\left[ \\begin{array}{cc} \n",
    "a_{01} & a_{02} \\\\\n",
    "0 & 0\n",
    "\\end{array}\\right], &  M_2(x)=\\left[ \\begin{array}{cc} \n",
    "b_{11} & b_{12} \\\\\n",
    "b_{21} & b_{22}\n",
    "\\end{array}\\right]  \\\\\n",
    "M_3(x)=\\left[ \\begin{array}{cc} \n",
    "c_{11} & c_{12} \\\\\n",
    "c_{21} & c_{22}\n",
    "\\end{array}\\right], &  M_4(x)=\\left[ \\begin{array}{cc} \n",
    "1 & 0 \\\\\n",
    "1 & 0\n",
    "\\end{array}\\right]  \\\\\n",
    "\\end{array}$$试求状态序列$y$以start为起点，stop为终点所有路径的非规范化概率及规范化因子。\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/11-5-Example11.2-State-Path.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图11-5 状态路径</div></center>  \n",
    "\n",
    "**解答：**  \n",
    "&emsp;&emsp;题中已知$M_1,M_2,M_3,M_4$，矩阵中的参数都是已知，已知了矩阵相当于已知条件随机场中的模型形式，以及所有的特征函数和特征向量。  \n",
    "&emsp;&emsp;所求的非规范化概率就是4个矩阵相乘，因为$M$都是矩阵，需要计算是哪个元素相乘，计算非规范化概率不考虑前面的$\\displaystyle \\frac{1}{Z(x)}$（即规范化因子），$M$相当于第10章隐马尔可夫模型的状态转移矩阵，初始的概率$\\pi$相当于$M_1$的矩阵中，可知$P(y_1=1)\\varpropto a_{01}，P(y_1=2)\\varpropto a_{02}$。  \n",
    "&emsp;&emsp;为什么是非规范化？因为在第10章隐马尔可夫模型中，每一个状态转移概率矩阵中每一行的和概率等于1，这样就保证了这是一个条件概率分布，但是在矩阵$M$中，求概率的时候，并没有考虑到前面的规范化因子，所以在矩阵$M$中每一行的和并不是1。当考虑状态转移关系时，没有考虑这是一个概率，如果求解$P(y_1,y_2,y_3)$联合概率分布，就需要规范化因子，求解局部概率，不考虑规范化。  \n",
    "  \n",
    "（1）要计算$y=(1,1,1)$路径的非规范化概率，从矩阵$M_1$中可得$P(y_0=1,y_1=1)=a_{01}$，从矩阵$M_2$中可得$P(y_1=1,y_2=1)=b_{11}$，从矩阵$M_3$中可得$P(y_2=1,y_3=1)=c_{11}$，从矩阵$M_4$中可得$P(y_3=1,y_4=1)=1$，所以$y=(1,1,1)$路径的非规范化概率为$a_{01}b_{11}c_{11}$，同理可得$y=(1,2,1)$路径的非规范化概率为$a_{01}b_{12}c_{21}$，可得到8个非规范化概率分别是：$$\\begin{array}{cccc} \n",
    "a_{01}b_{11}c_{11}, & a_{01}b_{11}c_{12}, & a_{01}b_{12}c_{21}, & a_{01}b_{12}c_{22} \\\\\n",
    "a_{02}b_{21}c_{11}, & a_{02}b_{21}c_{12}, & a_{02}b_{22}c_{21}, & a_{02}b_{22}c_{22}\n",
    "\\end{array}$$（2）计算规范化因子，因为要保证概率和为1，所以规范化因子$Z(x)$是8个规范化概率的和$Z(x)=a_{01}b_{11}c_{11}+a_{01}b_{11}c_{12}+a_{01}b_{12}c_{21}+a_{01}b_{12}c_{22}+a_{02}b_{21}c_{11}+a_{02}b_{21}c_{12}+a_{02}b_{22}c_{21}+a_{02}b_{22}c_{22}$  \n",
    "\n",
    "### 对比矩阵$M$和状态转移矩阵$A$\n",
    "1. 矩阵$A$是严格的条件概率分布，每一行的和为1，但是$M$没有要求  \n",
    "2. 在隐马尔可夫模型中，状态转移概率$A$是不随状态$i$变化的，在CRF中并没有假设状态是不能变的，参数会更多，模型也会更灵活，所以矩阵表示为$M_i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
